package com.liyghting.datastructurealgorithm.sort;

/**
 * 基数排序 时间复杂度是线性的，即是O(n)
 *
 * 基数排序对排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之前有递进的关系，如果数据a的高位比数据b要大，剩下的低位就不用比较了。
 * 除此以外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂达不到O(n)
 *
 * 比如10万手机号从小到大排序
 * 
 * @author LiYiGuang
 * @date 2020/1/16 11:13
 */
public class RadixSort {
    /**
     * 基数排序
     * 1.求最大位
     * 2.分割出独立的位，按该位来进行计数排序
     * 3.循环
     * @param arr
     * @param n
     */
	public static void radixSort(int[] arr, int n) {
		if (arr == null || n <= 1)
			return;
		int max = arr[0];
		for (int i = 1; i < n; i++) {
			if (max < arr[i])
				max = arr[i];
		}
		int maxbit = 1;
		while (max >= 10) {
			maxbit++;
			max /= 10;
		}
		// 计数
		int[] count = new int[10];
		int[] tmp = new int[n];
		int radix = 1;
        for (int i = 0; i < maxbit; i++) {
            for (int j = 0; j < 10; j++) {
                count[j] = 0;
            }
            // 以下是计数排序
            for (int j = 0; j < n; j++) {
                int k = (arr[j] / radix ) % 10; // 取指定位的数字
                count[k]++; // 指定位的数字的个数
            }
            for (int j = 1; j < 10; j++) {
                count[j] = count[j] + count[j-1]; // 顺序累加，用于定位
            }
            for (int j = n - 1; j >= 0 ; j--) {
                int k = (arr[j] / radix ) % 10; // 取指定位的数字
                int index = count[k] - 1;
                tmp[index] = arr[j];
                count[k]--;
            }
            for (int j = 0; j < n; j++) {
                arr[j] = tmp[j];
            }
            radix *= 10;
        }

	}

    public static void print(int[] a, int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = new int[] { 11, 81, 32, 96, 78, 10, 22, 5, 111 };
        radixSort(arr, 9);
        print(arr, 9);
    }
}
